public class SortColors {
    // leetcode 颜色分类
    // https://leetcode.cn/problems/sort-colors/description/?envType=study-plan-v2&envId=top-100-liked

    /**
     * left指向0的最后一个位置，right指向right的第一个位置
     * left初始化为-1，right初始化为nums.length
     * 遍历数组，当遇到n为0的时候就交换++left和i的元素，然后i++
     * 如果遇到1，那么直接i++
     * 如果遇到2，那么就交换--right和i的元素，这里不i++，因为交换之后的i位置的元素是没有检查的
     * 所以需要继续检查
     * @param nums
     */
    public void sortColors(int[] nums) {
        int left = -1, right = nums.length, i = 0;
        while (i < right) {
            if (nums[i] == 0) {
                swap(nums, ++left, i++);
            }else if (nums[i] == 1) {
                i++;
            }else {
                swap(nums, --right, i);
            }
        }
    }

    private void swap(int[] nums, int x, int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }
}
